package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaoxie
 * create: 2025-01-20 20:44
 * @BelongsProject: untitled
 * @BelongsPackage: leetcode
 * description:
 */
public class Text {
    /**
     * @description: 77. 组合
     *  <a href="https://leetcode.cn/problems/combinations/description/">...</a>
     *  回溯加剪枝
     * @author: xiaoxie
     * @date: 2025/1/20 20:52
     * @param:
     * @return:
     **/
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int m;
    public List<List<Integer>> combine(int n, int k) {
        m = k;
        dfs(n);
        return res;
    }
    public void dfs(int i) {
        if(path.size() == m) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int j = i; j >=  m - path.size();j--) {
            path.add(j);
            dfs(j-1);
            path.remove(path.size() -1);
        }
    }

}
